1268A - Long Beautiful Integer - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll mod = 1e8;
priority_queue<ll, vector<ll>, greater<ll> > minh;
priority_queue<ll> maxh;

ll dp[202][101][101][2];



ll gcdExtended(ll a, ll b, ll* x, ll* y)
{


    if (a == 0) {
        *x = 0, *y = 1;
        return b;
    }


    ll x1, y1;
    ll gcd = gcdExtended(b % a, a, &x1, &y1);


    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}


ll modInverse(long long int A, long long int M)
{
    ll x, y;
    ll g = gcdExtended(A, M, &x, &y);
    if (g != 1)
        return -1;
    else {

        ll res = (x % M + M) % M;
        return res;
    }
}

ll check(string s,string t,ll n)
{
    for(int i=0;i<n;i++)
    {
        if(t[i]>s[i])
            return 1;
        else if(t[i]==s[i])
            continue;
        else
            return 0;
    }

    return 1;
}



int main()
{
        ios_base::sync_with_stdio(false);
    	cin.tie(NULL);

        ll n,k;
        cin>>n>>k;

        string s;
        cin>>s;

        string t=s;
        for(int i=k;i<n;i++)
        {
            t[i] = t[i%k];
        }

        if(check(s,t,n))
        {
            cout<<t.length()<<endl;
            cout<<t<<endl;
        }
        else
        {
            ll j=k-1;
            for(j = k-1;j>=0;j--)
            {

                if(t[j]=='9')
                    continue;
                else
                    break;
            }

            for(int i = j+1;i<=k-1;i++)
                t[i] = '0';

            t[j] = char((t[j]-'0')+1 + '0');

            for(int i=k;i<n;i++)
            {
                t[i] = t[i%k];
            }

            cout<<t.length()<<endl;
            cout<<t<<endl;


        }










}